package monoqueue;

import java.util.LinkedList;

/**
 * @author pengfei.hpf
 * @date 2020/2/20
 * @verdion 1.0.0
 * 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
 *
 * 示例: 
 *
 * 输入: s = 7, nums = [2,3,1,2,4,3]
 * 输出: 2
 * 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
 * 进阶:
 *
 * 如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MinSubArrayLen {
    public int minSubArrayLen(int s, int[] nums){
        if(nums == null || nums.length == 0){
            return 0;
        }
        long curSum = 0;
        int minLength = nums.length;
        LinkedList<Integer> queue = new LinkedList<>();
        for(int i = 0; i < nums.length; i ++){
            curSum += nums[i];
            queue.addLast(nums[i]);
            if(curSum >= s){
                int first = queue.peek();
                while(!queue.isEmpty() && curSum - first > s){
                    queue.removeFirst();
                    curSum -= first;
                    first = queue.peek();
                }
                if(minLength > queue.size()){
                    minLength = queue.size();
                }
            }
        }
        if(curSum < s){
            return 0;
        }
        return minLength;
    }
}
